package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/16 15:11
 * @description: 即物品可分开
 */
public class _053_分数背包空间问题 {


    @Test
    public void test1() {

        Item item = new Item(1, 3, 5);
        Item item2 = new Item(2, 4, 6);
        Item item3 = new Item(3, 5, 7);
        Item item4 = new Item(4, 6, 8);
        Item item5 = new Item(5, 7, 9);

        System.out.println(getMaxValue(new Item[]{item, item2, item3, item4, item5}, 10));
    }

    /**
     * 分背包问题(注:没考虑小数)
     * 1. 根据物品价值/重量 倒序排序
     * 2. 遍历物品,如果当前物品重量小于剩余重量,则直接加入背包,剩余重量减去当前物品重量
     *
     * @param items
     * @param maxWeight
     * @return
     */
    private int getMaxValue(Item[] items, int maxWeight) {
        int maxValue = 0;
        Arrays.sort(items, (o1, o2) -> o2.value / o2.weight - o1.value / o1.weight);
        for (int i = 0; i < items.length; i++) {
            if (maxWeight >= items[i].weight) {
                maxValue += items[i].value;
                maxWeight -= items[i].weight;
            } else {
                maxValue += items[i].value * maxWeight / items[i].weight;
                break;
            }
        }
        return maxValue;
    }

    private static class Item {
        private int id;
        private int weight;
        private int value;

        public Item(int id, int weight, int value) {
            this.id = id;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "id=" + id +
                    ", weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }
}
